/**
 * Created by ACER on 2019/3/23.
 */

/**
 * 排序算法测试类
 */
public class SortTest {
    public static void main(String[] args) {
        int[] start = getList(10);
//        long l1 = System.currentTimeMillis();
//        //冒泡排序
//        bubbling(start);
//        System.out.println("\n冒泡排序时间>>>>" + (System.currentTimeMillis() - l1));
//        long l2 = System.currentTimeMillis();
//        //快速排序
//        int[] quickSort = quickSort(start, 0, start.length - 1);
//        System.out.println("快排时间>>>>" + (System.currentTimeMillis() - l2));
//        printSortResult("快速排序", quickSort);
//        //选择排序
//        chooseSort(start);
//        //堆排序
//        int[] heapSort = heapSort(start);
//        printSortResult("堆排序", heapSort);
//        //直接插入排序
//        insertSort(start);

        //归并排序
        mergeSort(start, 0, start.length - 1);
        printSortResult("归并排序", start);
    }

    //生成排序的数字（1-100）
    public static int[] getList(int size) {
        System.out.print("排序前数字：\t");
        int baseNum[] = new int[size];
        for (int i = 0; i < size; i++) {
            int v = (int) (Math.random() * 100);
            baseNum[i] = v;
            System.out.print(v + "\t");
        }
        return baseNum;
    }

    //冒泡排序法----第一次遍历将最小的数放到最前面，接着将第二小的数放在第二个位置，每次循环遍历
    public static int[] bubbling(int[] beforeNum) {
        //缓存元素
        Integer temp;
        for (int i = 0; i < beforeNum.length - 1; i++) {
            for (int j = beforeNum.length - 1; j > i; j--)
                if (beforeNum[j - 1] > beforeNum[j]) {
                    temp = beforeNum[j];
                    beforeNum[j] = beforeNum[j - 1];
                    beforeNum[j - 1] = temp;
                }
        }
        printSortResult("冒泡排序", beforeNum);
        return beforeNum;
    }


    //快速排序法 ----选定一个初始值s，2个哨兵i（开始位置）j（结束位置）i从前往后遍历，j从后往前遍历（先）
//j找比s小的数，i找比s大的数，交换，如果ij相遇，s与i交换。此时，s左边的数比s小，s右边的数比s大
//对左边与右边的数分别再进行操作
    public static int division(int[] list, int left, int right) {
        //选择一个基准元素值s
        int baseNum = list[left];
        while (left < right) {
            //从数组右端开始找,找比baseNum小的数
            while (left < right && list[right] >= baseNum)
                right--;
            //将j赋值给基准值
            list[left] = list[right];
            //从数组左端开始，找比基准值大的数
            while (left < right && list[left] <= baseNum)
                left++;
            //将left值赋给右边
            list[right] = list[left];
        }
        list[left] = baseNum;
        return left;
    }

    //快速排序
    public static int[] quickSort(int[] startNum, int left, int right) {
        if (left < right) {
            //分割数据
            int i = division(startNum, left, right);
            quickSort(startNum, left, i - 1);
            quickSort(startNum, i + 1, right);
        }
        return startNum;
    }

    //选择排序
    public static int[] chooseSort(int[] list) {

        for (int i = 0; i < list.length - 1; i++) {
            //假设下标值最小
            int tempIndex = i;
            for (int j = i + 1; j < list.length - 1; j++) {
                if (list[tempIndex] > list[j]) {
                    tempIndex = j;
                }
            }
            //数据交换
            int temData = list[tempIndex];
            list[tempIndex] = list[i];
            list[i] = temData;

        }

        printSortResult("选择排序", list);
        return list;
    }


    //堆排序
    //调整堆方法
    public static void heapAdjust(int[] list, int parent, int length) {
        //temp保存当前父节点
        int temp = list[parent];

        //得到左孩子(这可是二叉树的定义，大家看图也可知道)
        int child = 2 * parent + 1;

        while (child < length) {
            //如果parent有右孩子，则要判断左孩子是否小于右孩子
            if (child + 1 < length && list[child] < list[child + 1])
                child++;

            //父亲节点大于子节点，就不用做交换
            if (temp >= list[child])
                break;

            //将较大子节点的值赋给父亲节点
            list[parent] = list[child];

            //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
            parent = child;

            //找到该父亲节点较小的左孩子节点
            child = 2 * parent + 1;
        }
        //最后将temp值赋给较大的子节点，以形成两值交换
        list[parent] = temp;
    }

    //堆排序算法
    public static int[] heapSort(int[] list) {
        //list.Count/2-1:就是堆中父节点的个数
        for (int i = list.length / 2 - 1; i >= 0; i--) {
            heapAdjust(list, i, list.length);
        }

        //最后输出堆元素
        for (int i = list.length - 1; i > 0; i--) {
            //堆顶与当前堆的第i个元素进行值对调
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;

            //因为两值交换，可能破坏根堆，所以必须重新构造
            heapAdjust(list, 0, i);
        }
        return list;
    }


    //直接插入排序法（类似斗地主理牌）
    public static void insertSort(int[] list) {

        //无序序列
        for (int i = 1; i < list.length; i++) {
            int temp = list[i];
            int j;
            for (j = i - 1; j < i && temp < list[j]; j--) {
                list[j + 1] = list[j];
            }
            list[j + 1] = temp;
        }
        printSortResult("直接插入排序", list);
    }


    public static void printSortResult(String name, int[] list) {
        System.out.printf("\n" + name + "\t");
        for (int i : list) {
            System.out.printf(i + "\t");
        }
    }


    //补充
    //归并排序
    public static void mergeSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2;
            mergeSort(list, low, middle);
            mergeSort(list, middle + 1, high);
            merge(list, low, high);
//            merge(list, low, high);
        }
    }
    //合并
//    public static void merge(int[] list, int low, int high) {
//        int[] temp = new int[high - low + 1];
//        int mid = (low + high) / 2;
//        int i = low, j = mid + 1;
//        int k = 0;
//        while (i <= mid && j <= high) {
//            if (list[j] < list[i]) {
//                temp[k++] = list[j++];
//            } else {
//                temp[k++] = list[i++];
//            }
//        }
//        while (i <= mid) {
//            temp[k++] = list[i++];
//        }
//        while (j <= high) {
//            temp[k++] = list[j++];
//        }
//        k = 0;
//        for (i = low; i <= high; i++, k++) {
//            list[i] = temp[k];
//        }
//
//    }

    //合并数
    public static void merge(int[] list,int low ,int high){
        int[] temp = new int[high-low+1];
        int mid = (low+high)/2;
        int i=low,j=mid+1,k=0;
        //将数按顺序放入temp
        while (i<=mid&&j<=high){
            if (list[i]<list[j]){

                temp[k++] = list[i++];
            }
            else {
                temp[k++] = list[j++];
            }
        }
        //比后面所有数都大的数
        while (i<=mid){
            temp[k++] = list[i++];
        }
        //比前面所有数都大的数
        while (j<=high){
            temp[k++] = list[j++];
        }
        //放入list中
        k=0;
        for (i=low;i<=high;i++,k++){
            list[i] = temp[k];
        }
    }
}

